'''
https://leetcode.cn/problems/campus-bikes/description
'''
import heapq
from typing import List


class Solution:
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> List[int]:
        n, m = len(workers), len(bikes)

        def manhattan_distance(p1, p2):
            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

        res = [-1] * n
        bike_used = [False] * m
        pq = []     # 枚举所有的 (人车距离, 人id, 车id)
        for i in range(n):
            for j in range(m):
                heapq.heappush(pq, (manhattan_distance(workers[i], bikes[j]), i, j))

        while pq:
            while pq and (res[pq[0][0]] != -1 or bike_used[pq[0][1]]):
                heapq.heappop(pq)
            if not pq: break
            _, work, bike = heapq.heappop(pq)
            res[work] = bike
            bike_used[bike] = True
        return res
